package simple;

import sword.offer.common.GenerateList;
import sword.offer.common.ListNode;

/**
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * */
public class PalindromeLinkedList {

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.isPalindrome(GenerateList.generate(new int[]{1,1,2,1}));
    }

    /**
     * 快慢指针法找到链表的中间结点。
     * fast指针每次走两步  slow指针每次走一步 当fast指向最后一个结点的时候，slow就指向中间结点。
     * 然后fast回到中间结点的下一个结点，然后开始将后半部分的链表进行反转。
     * 然后slow回到链表head， fast处于链表的tail。两个指针开始往中间靠，知道碰到位置
     *
     * */
    static class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head.next == null){
                return true;
            }
            ListNode fast = head.next;
            ListNode slow = head;
            // 找到中间结点
            while (fast.next != null && fast.next.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            fast = slow.next;
            slow.next = null;
            slow = head;
            ListNode pre = null;
            while(fast.next != null){
                ListNode tempNode = fast.next;
                fast.next = pre;
                pre = fast;
                fast = tempNode;
            }
            fast.next = pre;
            while(fast != null && slow != null){
                if(fast.val != slow.val){
                    return false;
                }
                fast = fast.next;
                slow = slow.next;
            }

            return true;
        }
    }
}
